package src.DisciplesPlan.链表;

/**
 * 链表的构造方式1
 */

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }
}

public class MyLinkedList {
    public static void main(String[] args) {
        Node head = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        // 测试反转链表的前两个结点
        head = reverse(head, 2);

        // 链表的遍历
        Node p = head;
        while (p != null) {
            System.out.println(p.data);
            p = p.next;
        }
    }

    /**
     * 反转输出链表
     * @param p 头结点
     */
    public static void reverse(Node p) {
        if (p == null)
            return;
        reverse(p.next);
        System.out.println(p.data);
    }

    /**
     * 反转链表，可以自定义反转个数
     * @param head 头结点
     * @param n 反转的结点个数
     * @return
     */
    public static Node reverse(Node head, int n) {
        // 如果反转到最后一个结点则直接返回
        if (n == 1) {
            return head;
        }
        // 递归查找到需要反转的最后两个结点
        Node tail = head.next;
        Node p = reverse(head.next, n - 1);
        // 依次反转最后两个结点
        head.next = tail.next;
        tail.next = head;
        // 返回新链表的头结点，也即原链表需要反转的最后一个结点，注意，每一层返回的p结点都是一样的
        return p;
    }
}
